/**
 * 给定一个二维网格 grid ，其中：
 *
 * '.' 代表一个空房间
 * '#' 代表一堵
 * '@' 是起点
 * 小写字母代表钥匙
 * 大写字母代表锁
 * 我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
 *
 * 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
 *
 * 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
 *
 *https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/
 * 思路：bfs + 状态压缩
 */
class ShortestPathAllKeys {
    public int shortestPathAllKeys(String[] grid) {
        Queue<int[]> q = new LinkedList<>();
        int n = grid.length, m = grid[0].length(), flag = 0;
        int[] d = new int[]{1, 0, -1, 0, 1};
        boolean[][][] vis = new boolean[n][m][1 << 7];
        char[][] g = new char[n][m];
        for (int i = 0; i < n; i++) g[i] = grid[i].toCharArray();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@') q.add(new int[]{i, j, 0, 1});
                if (g[i][j] >= 'a' && g[i][j] <= 'f') flag |= (1 << (g[i][j] - 'a'));
            }
        }
        while (!q.isEmpty()) {
            int[] tem = q.poll();
            int x = tem[0], y = tem[1], mask = tem[2], step = tem[3];
            for (int i = 0; i < 4; i++) {
                int fx = x + d[i];
                int fy = y + d[i + 1];
                int st = mask;
                if (fx < 0 || fy < 0 || fx >= n || fy >= m || g[fx][fy] == '#') continue;
                if (g[fx][fy] >= 'A' && g[fx][fy] <= 'F' && ((mask & (1 << (g[fx][fy] - 'A'))) == 0)) continue;
                if (g[fx][fy] >= 'a' && g[fx][fy] <= 'f') st |= (1 << (g[fx][fy] - 'a'));
                if (!vis[fx][fy][st]) {
                    q.add(new int[]{fx, fy, st, step + 1});
                    vis[fx][fy][st] = true;
                }


                if (st == flag) return step;
            }
        }
        return -1;
    }
}
 
